#include <iostream>
#include <map>
using namespace std;
class Node
{
public:
    int val;
    Node *next;
    Node *random;

    Node(int _val)
    {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
class Solution
{
public:
    Node *copyRandomList(Node *head)
    {
        Node *copyhead = nullptr, *copytail = nullptr;
        map<Node *, Node *> Nodemap;
        Node *cur = head;

        while (cur)
        {
            if (cur == head)
            {
                copyhead = copytail = new Node(cur->val);
            }
            else
            {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            Nodemap[cur] = copytail;
            cur = cur->next;
        }
        copytail = copyhead;
        cur = head;
        while (copytail)
        {
            if (cur->random == nullptr)
            {
                copytail->random = nullptr;
            }
            else
            {
                copytail->random = Nodemap[cur->random];
            }
            copytail = copytail->next;
            cur = cur->next;
        }
        return copyhead;
    }
};